package Test;

import java.util.List;

public class 反转链表 {
    /*************                      第一种                   *************************************************/
    /*********           递归             *********/
    ListNode reverse(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode last=reverse(head.next);
        head.next.next=head;
        head.next=null;
        return last;
    }


    /********************        迭代       *************************/
    ListNode reverse01(ListNode head) {
        ListNode pre=null;
        ListNode cur=head;


        while (cur!=null){
            ListNode nxt=cur.next;
            cur.next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }

    /**********************************        第二种         ****************************************************/
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left==1){
            return reverseBetweenleftandright(head,right);
        }else {
            head.next=reverseBetween(head.next,left-1,right-1);
            return head;
        }

    }
    ListNode nxt;
    ListNode reverseBetweenleftandright(ListNode head,int right){
       if(right==1){
           nxt=head.next;
           return head;
       }else {
           ListNode last=reverseBetweenleftandright(head.next,right-1);
           head.next.next=head;
           head.next=nxt;
           return last;
       }

    }

}
